package com.lq.test;

import java.util.ArrayList;
import java.util.List;
/**
 * 给定一个数组，数组中每一个值代表该位置上的其他数组的大小
 * 需要在这些其他数组中每一个取一个值，所有的可能性
 * 返回所有的组合可能
 * 如： 从000 到 321 ，321代表 有三个数组，第一个大小3，第二个大小2，第三个大小1
 * 则这三个数组中取一个的所有可能序列（将加数设置成1即可）产生：
 * [0, 0, 0]
 * [1, 0, 0]
 * [2, 0, 0]
 * [0, 1, 0]
 * [1, 1, 0]
 * [2, 1, 0]
 * [0, 2, 0]
 * [1, 2, 0]
 * [2, 2, 0] 
 * 
 * 
 * @author liuqiang
 *
 */
public class CalculateWestly {

    //是否和最大知道的值一样
	public static boolean isMax(List<Integer> start,List<Integer> max){
		for(int i = 0 ;i <max.size(); i ++){
			if(start.get(i)+1 != max.get(i)){
				return false;
			}
		}
		return true;
	}
	
	//是否已经到最大或者超过最大值了
	public static boolean isOverflow(List<Integer> start,List<Integer> max,Integer added){
		List<Integer> startCopy = copyList(start);
		List<Integer> maxCopy = copyList(max);
		Integer addedCopy = added;
		if(isMax(startCopy,maxCopy))
			return true;
		int up = calcAddForUp(startCopy.get(0),addedCopy,maxCopy.get(0));
		for(int i = 0; i < startCopy.size() -1 ; i++){
			if(up > 0){
				Integer upedInte = startCopy.get(i+1) + up;
				startCopy.set(i+1, upedInte);
				up = calcAddForUp(startCopy.get(i+1),0,maxCopy.get(i+1));
			}
		}
		if(up > 0)
			return true;
		else return false;
	}
	//拷贝一个数组
	public static List<Integer> copyList(List<Integer> src){
		List<Integer> target = new ArrayList<Integer>();
		for(Integer temp : src){
			target.add(temp);
		}
		return target;
		
	}
	//加到指定值，越界结束
	
	//多位数加法
	public static List<Integer> calcAdd(List<Integer> start,List<Integer> max,Integer added){
		List<Integer> result = new ArrayList<Integer>();
		int size = start.size();
		int src = calcAddForSrc(start.get(0),added,max.get(0));
		int up = calcAddForUp(start.get(0),added,max.get(0));
		Integer srcInte = new Integer(src);
		start.set(0, srcInte);
		if(size > 1){
			for(int i =0 ; i < size-1; i++){
				if(up > 0){
					Integer upedInte = start.get(i+1)+up;
					start.set(i+1, upedInte);
					int newsrc = calcAddForSrc(start.get(i+1),0,max.get(i+1));
					up = calcAddForUp(start.get(i+1),0,max.get(i+1));
					Integer newsrcInte = new Integer(newsrc);
					start.set(i+1, newsrcInte);
				}
				
			}
		}
		result = copyList(start);
		return result;
	}
	
	//计算进位数
	public static int calcAddForUp(Integer source,Integer added,Integer uped){
		int sum = source + added;
		int up = sum/uped;
		return up;
	} 
	//计算原始数进位后的余数
	public static int calcAddForSrc(Integer source,Integer added,Integer uped){
		int sum = source + added;
		return sum % uped;
	}
	//个人收藏 二进制加法
	public static String addBinary(String a, String b) {
		int len = Math.max(a.length(), b.length());
		String res = "";
		int carry = 0;
		for (int i = 0; i < len; i++) {
			int ca = i < a.length() ? a.charAt(a.length() - i - 1) - '0' : 0;
			int cb = i < b.length() ? b.charAt(b.length() - i - 1) - '0' : 0;
			res = (ca + cb + carry) % 2 + res;
			carry = (ca + cb + carry) / 2;
		}
		if (carry > 0)
			res = carry + res;
		return res;
	}
	
	public static void main(String[] args) {
		//--------------start 测试---------------
		List<Integer> init = new ArrayList<Integer>();
		List<Integer> max = new ArrayList<Integer>();
		init.add(0);
		init.add(0);
		init.add(0);
		max.add(3);
		max.add(3);
		max.add(1);
		Integer addedt = 1;
		System.out.println(calcAdd(init,max,0));
		while(!isOverflow(init,max,addedt)){
			List<Integer> re = calcAdd(init,max,addedt);
			/*for(int i=re.size()-1;i>=0;i--){
				System.out.print(re.get(i));
			}*/
			System.out.println(re);
		}
		System.out.println("-----------");
		System.exit(0);
		//-------------end 测试-----------------
	}
}
